package com.light.sword.concurrent

import java.util.concurrent.ForkJoinPool
import java.util.concurrent.ForkJoinTask
import java.util.concurrent.RecursiveTask

/**
分治思想用递归实现的经典案例就是斐波那契数列了。
斐波那契数列：1、1、2、3、5、8、13、21、34、……
公式 ：
F(1)=1，
F(2)=1,
F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
 */
class FibonacciRecursiveTask(val n: Long) : RecursiveTask<Long>() {

    override fun compute(): Long {
        if (n <= 1) {
            return n
        }
        val f1 = FibonacciRecursiveTask(n - 1)
        val f2 = FibonacciRecursiveTask(n - 2)
        ForkJoinTask.invokeAll(f1, f2)
        return f2.join() + f1.join()
    }
}

class Fibonacci(val n: Long) {
    fun compute(): Long {
        if (n <= 1) {
            return n
        }
        return Fibonacci(n - 1).compute() + Fibonacci(n - 2).compute()
    }
}


fun main(args: Array<String>) {

    val t1 = System.currentTimeMillis()
    run {
        val fib = FibonacciRecursiveTask(30)
        val forkJoinPool = ForkJoinPool(4) // 最大并发数
        val f = forkJoinPool.invoke(fib)
        println("f=$f") // f=102334155
    }

    val t2 = System.currentTimeMillis()
    run {
        val fib = Fibonacci(40)
        val v = fib.compute()
        println("v=$v")
    }

    val t3 = System.currentTimeMillis()

    println("t2-t1:${t2 - t1}")
    println("t3-t2:${t3 - t2}")
}

/*
输出:
f=832040
v=102334155
t2-t1:393
t3-t2:2922
*/